풀이

정말 빡빡하게도, 정석적인 풀이법의 소요시간과 시간초과 기준점이 딱 붙어있게 설계된 문제인 것 같다. 그래서 람다함수에서 병목현상이 일어나 시간초과가 뜬 것 같다. 하지만 람다함수 + 나의 아주 제너럴한 이분탐색 코드를 std::upper_bound 코드로 교체하자 바로 Pass가 떴다. upper_bound 함수는 간단히 주어진 범위 안에서 value <= *it 인지 아닌지만 검사하기 때문에 속도가 빠르다.

어쨌든 기본적인 풀이법은 완전 동일하다.

1. 말의 위치에 대해서만 정렬을 수행한다. (소 ↔ 말 벡터는 사실 뭘 먼저 해도 상관은 없음)
2. 어떤 소 cow에 대해서 말과의 거리를 최소로 하는 말을 찾는다.
3. 그 말과의 거리가 min_dist 보다 작으면 count와 min_dist의 값을 초기화한다.
   1. 같으면 count 값을 1 증가시킨다.

2번 과정을 빠르게 수행하는 것이 이 문제의 관건인데, 이를 위해서 이분탐색을 활용한다. 이때 거리를 계산한다고 절댓값을 취해선 절대로 안된다. 참/거짓 구성이 흐트러질 수 있기 때문이다. 그러면 어떻게 하느냐? 이분탐색을 두 번 하는 것에서 아이디어는 출발한다.

1. 소 ≤ 말을 만족하는 첫번째 말을 찾는다.
2. 말 ≤ 소를 만족하는 첫번째 말을 찾는다.

이렇게 두고보니 사실 1번말을 찾으면 자연스럽게 2번말이 튀어나오게 된다. 1번말에 바로 이전 말이 2번말이기 때문!

sol1

나의 제너럴한 이분탐색 알고리즘이다. T로는 인덱스(숫자)가 와도 되고, STL 처럼 이터레이터가 와도 전혀 무관하다. 핵심은 predicate 안에 있기 때문이다. 함수 이름에서부터 predicate가 true를 만족하는 바로 첫번째 녀석을 이 함수가 찾아주기 때문이다.

/**
F-...-F-F-F-T-T-T-...-T
            ^
*/
template <typename T, class Predicate>
inline T first_true(T begin, T end, Predicate const &pred) {

  T l = begin;
  T r = end;
  while (l < r) {
    T mid = l + (r - l) / 2;
    if (pred(mid)) {
      // next range is [l, mid)
      r = mid;
    } else {
      // next range is [mid + 1, r)
      l = mid + 1;
    }
  }
  return l;
}

아래는 나의 말로 쓴 수도코드를 그대로 c++ 코드로 옮겨적은 모습이다. evaluate 라는 람다함수를 활용하여 코드중복을 해소했다. 왜 두번이나 평가하냐고? 1번말이 첫번째 evaluate이고 2번말이 두번째 evaluate이기 때문.

/**
@return:
 - first: 가장 가까운 쌍의 거리
 - second: 그러한 거리를 갖는 쌍의 개수
*/
inline pair<int, int> solution(vector<int> const &cows, vector<int> &horses) {
  //
  std::sort(horses.begin(), horses.end());

  int min_dist = std::numeric_limits<int>::max();
  int count = 0;

  auto evaluate = [&min_dist, &count](int dist) {
    if (dist < min_dist) {
      min_dist = dist;
      count = 1;
    } else if (dist == min_dist) {
      count += 1;
    }
  };

  for (auto const &cow : cows) {
    // 어떤 소에 대하여 (소 <= 말) 조건을 만족시키는 첫번째 말을 고른다.
    // 그 말의 바로 이전 말과 비교하여 더 가까운 놈을 선택한다.
    auto horse_itr = first_true(horses.begin(), horses.end(),
                                [cow](auto itr) { return cow <= *itr; });
    if (horse_itr != horses.end()) {
      evaluate(abs(cow - *horse_itr));
    }
    if (horse_itr != horses.begin()) {
      evaluate(abs(cow - *(horse_itr - 1)));
    }
  }

  return std::make_pair(min_dist, count);
}

이렇게만 보면 참 깔끔하고 기분이 좋아지는데… 결과는 알다시피 시간초과였다.

sol2

그래서 무지성으로 horses 벡터를 만들지 않고 메인함수에서 standard input으로 받는 족족 이분탐색을 하면 어떨까 해서 그렇게 해봤지만 마찬가지였다. 결국 나의 이분탐색 코드를 버리고 의미적으로 완전 동일한 upper_bound 함수를 사용하기로 결정했다.

cow를 먼저 입력받으니 얘를 벡터에 넣어 정렬하기로 했다. 이제 각 horse마다 가장 가까운 cow를 찾으면 되는데, 그 과정을 단순히 upper_bound로 교체했을 뿐인데 바로 Pass가 나와버려 얼탱이 없었다.

람다함수가 병목현상을 만드는지에 관해서는 좀 더 조사할 필요가 있다.

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  freopen("sample_input.txt", "r", stdin);

  int t = 0;
  cin >> t;

  for (int tc = 1; tc <= t; ++tc) {

    int n;
    int m;
    int c1;
    int c2;
    cin >> n >> m >> c1 >> c2;
    int dist_x = abs(c1 - c2);
    vector<int> cows;
    vector<int> horses;

    for (int i = 0; i < n; ++i) {
      int cow;
      cin >> cow;
      cows.push_back(cow);
    }
    // cow를 정렬하고 horse는 벡터에 넣지말고 바로 bin_search
    std::sort(cows.begin(), cows.end());

    int dist_z = std::numeric_limits<int>::max();
    int count = 0;

    auto evaluate = [&dist_z, &count](int dist) {
      if (dist < dist_z) {
        dist_z = dist;
        count = 1;
      } else if (dist == dist_z) {
        count += 1;
      }
    };

    for (int i = 0; i < m; ++i) {
      int horse;
      cin >> horse;

      // 어떤 말에 대하여 (말 <= 소) 조건을 만족시키는 첫번째 말을 고른다.
      // 그 말의 바로 이전 말과 비교하여 더 가까운 놈을 선택한다.
      auto cow_itr = std::upper_bound(cows.begin(), cows.end(), horse);
      if (cow_itr != cows.end()) {
        evaluate(abs(horse - *cow_itr));
      }
      if (cow_itr != cows.begin()) {
        evaluate(abs(horse - *(cow_itr - 1)));
      }
    }

    cout << "#" << tc << " " << dist_z + dist_x << " " << count << "\\n";
  }
  return 0;
}